Subject: Re: Conservative Sorting/Presv Order of Orig??
From: [email-masked] (Jos Horsmeier)
Date: Sun, 24 Apr 1994 07:07:43 GMT
Newsgroups: comp.programming

In article <[email-masked]> [email-masked] (Robert H. Cudmore) writes:

|	I am attempting to sort an array of elements A.  I have a Heap sort
|up and running, the problem is this:  I need the elements with equal keys
|to remain in their original order.  Heap sort with building(hiring) and 
|Sorting(firing) of the array into a heap and then into a sorted array seems
|to cause the destruction of the original order of all elements. 
|
|	Are there efficient O(nlogn) sorting routines that will preserve this
|original order?  Quicksort seems to do the same destructive ordering of
|the data where as a simple insertion sort does not.  I would like to stay
|away from linear complexity sorts and would also like to know if I can't
|stay away from them.

A cheap trick: for all elements A_1, A_2, ..., A_n add an integer tag
field to those records and initialize them with the values i for all A_i.
If two keys compare equal, compare the tag fields. That's all there is
to it. No two keys will compare equal in this case ...

I hope this helps you out,

kind regards,

Jos aka [email-masked]
----------------------------------------------------------------------------
I'm not hooked on nicotine, it's that I just can't do without it.